P3469 BLO-Blockade

这道题一看就是到好(shui)题,毕竟自己因long long的问题的错了几次。好吧,不废话,开始讲解:

这道题一看就是求无向图中,去掉一个点后无法连通的点对,但注意:

  1. (x,y)( x , y )(y,x)( y , x ) 算作不同的点
  2. 即使点被删除后,也要计入无法连通数,但显然他们是不联通的

首先 ii 跟其他n1n-1个点肯定不能互通。如果ii是割点,那么去掉ii之后的几个不同连通分量就不能互通,那我们现在就想办法求一下去掉ii后被切断的连通分量。先观察一下下图:

黄点是一个割点,我们先考虑以它为根的子树的联通情况:

我们用child[u]child[u]表示以uu为根的子树的大小,显然

child[u]=vuchild[v]child[u]=\sum_{v \in u}child[v]

这个我们可以在TarjanTarjan中算出。

我们再定义sumsum为当前u已经遍历到的子树的节点个数,ss为去掉uu点后子树中的点无法连通的情况。

那么,每次遍历子节点vv , s=s+sumchild[v]s=s+sum*child[v] , sum=sum+child[v]sum=sum+child[v]

现在在考虑子树内部与外部的联通情况,uu的子树大小为sumsum,外部节点为nsum1n-sum-1,去掉点uu后,这些点也是无法连通的,tt为去掉u点后子树中的点与外部的点无法连通的情况。

那么,t=sum(nsum1)t=sum*(n-sum-1)

结合注意事项1,2,我们可以得到:Ans[u]=[s+t+(n1)]2Ans[u]=[s+t+(n-1)]*2,这就是最后的答案了。

代码如下:

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 100000;
int n,m,x,y;
vector< int > Graph[ MAXN + 5 ];

void Read( int &x ) {
	int f = 1;
	x = 0;
	char s = getchar( );
	
	while( s < '0' || s > '9' ) {
		if( s == '-' ) f = -1;
		s = getchar( );
	}
	while( s >= '0' && s <= '9' ) {
		x = x * 10 + s - 48;
		s = getchar( );
	}
	x *= f;
}
void Write( long long x ) {
	if( x < 0 ) {
		x = -x;
		putchar('-');
	}
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + 48 );
}
int Max( int x , int y ) {
	return x > y ? x : y;
}
int Min( int x , int y ) {
	return x < y ? x : y;
}

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , child[ MAXN + 5 ] , depth;
long long Ans[ MAXN + 5 ];

void Tarjan( int u , int fa ) {
	dfn[ u ] = low[ u ] = ++ depth;
	child[ u ] = 1;
	//printf("%d %d\n",u,depth);
	long long sum = 0;
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( v == fa ) continue;
		
		if( !dfn[ v ] ) {
			Tarjan( v , u );
			child[ u ] += child[ v ];
			
			if( low[ v ] >= dfn[ u ] ) {
				Ans[ u ] += child[ v ] * sum;
				sum += child[ v ];
			}
			low[ u ] = Min( low[ u ] , low[ v ] );
		}
		
		else if( v != fa && dfn[ u ] > dfn[ v ] )
			low[ u ] = Min( low[ u ] , dfn[ v ] );
	}
	Ans[ u ] = ( Ans[ u ] + sum * ( n - sum - 1 ) + n - 1 ) * 2;
}

int main( ) {
	Read( n ) , Read( m );
	for( int i = 1 ; i <= m ; i ++ ) {
		Read( x ) , Read( y );
		Graph[ x ].push_back( y );
		Graph[ y ].push_back( x );
	}
	Tarjan( 1 , -1 );
	
	for( int i = 1 ; i <= n ; i ++ )
		Write( Ans[ i ] ) , putchar('\n');
	return 0;
}